package com.heyqing.topic.ClimbStairs_0070;

import java.util.Scanner;

/**
 * ClassName:ClimbStairs
 * Package:com.heyqing.topic.ClimbStairs_0070
 * Description:
 *
 * @Date:2024/9/10
 * @Author:Heyqing
 */
public class ClimbStairs {
    public int climbStairs(int n) {
        return FibonacciMatrix.fibonacci(n + 1);
    }


    public static void start() {
        Scanner sc = new Scanner(System.in);
        System.out.println("n:");
        int n = sc.nextInt();
        ClimbStairs climbStairs = new ClimbStairs();
        int way = climbStairs.climbStairs(n);
        System.out.println(way);
    }
}

class FibonacciMatrix {

    private static final int[][] FIB_MATRIX = {{1, 1}, {1, 0}};

    public static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return matrixPower(FIB_MATRIX, n - 1)[0][0]; // 直接返回结果矩阵的第一行第一列元素
    }

    private static int[][] matrixPower(int[][] matrix, int power) {
        int[][] result = {{1, 0}, {0, 1}};
        while (power > 0) {
            if ((power & 1) == 1) {
                result = multiply(result, matrix);
            }
            matrix = multiply(matrix, matrix);
            power >>= 1;
        }
        return result;
    }

    private static int[][] multiply(int[][] matrixA, int[][] matrixB) {
        int[][] result = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    result[i][j] += matrixA[i][k] * matrixB[k][j];
                }
            }
        }
        return result;
    }
}
